package com.gorkr.backtracking;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author gorkr
 * @date 2022/06/21 21:30
 **/
public class M39CombinationSum {
    private List<List<Integer>> res = new ArrayList<>();
    private LinkedList<Integer> track = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates.length==0){
            return res;
        }

        backTracking(candidates,target,0,0);
        return res;
    }

    private void backTracking(int[] candidates,int target, int sum, int start){

        if(sum==target){
            res.add(new LinkedList<>(track));
            return;
        } else if (sum > target) {
            return;
        }


        // 如何将左边的剪掉 这个start 是关键

        for (int i = start; i < candidates.length; i++) {
            // 做选择
            sum+=candidates[i];
            track.add(candidates[i]);
            backTracking(candidates,target,sum,i);  // 这里 start 传入i 是关键
            // 撤销
            sum-=candidates[i];
            track.removeLast();
        }

    }

    @Test
    public void test(){
        int[] candidates={2,3,6,7};
        int target = 7;
        System.out.println(combinationSum(candidates, target));
    }

}
    